// ms_grid_test_rand_multithread.cpp : Defines the entry point for the console application.
//


#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <signal.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <pthread.h>
#include <io.h>
#include <windows.h>

#define UPLEFT 0
#define UP 1
#define UPRIGHT 2
#define RIGHT 3
#define DOWNRIGHT 4
#define DOWN 5
#define DOWNLEFT 6
#define LEFT 7
#define USED 8

#define SAVEREQUIRED -1
#define BESTSCOREFOUND -2

#define MAINGAME 0

struct line
{
	char x;
	char y;
	char pos;
	char dir;
};

struct thread_data
{
	pthread_t thread;
	int no_pos;
	int score;
};

struct game_data
{
	char grid[60][60][9];//This is the table where the game is stored : 60*60 points, 0-7 : possibilities (directions see define), 8 : l empty or not
	int searching_state[1000][4];//This table contains the state of the algorithm, it's used to save the progress of the search. Format : (current possibility | max possibility | best possibility found | best score) for each floor of the tree
	struct line selected_lines[1000];//This table contains the list of the lines played, it's large enough to contain the largest theoric game
	struct line possibilities[400][100];//This table contains 100 possibilities for 400 floors max (large enough to contain the largest theoric game)
	char searching_range[4];//{min x, max x, min y, max y}
	int line_no;
	int score;
};

struct game_data * gd;//gd contains the main game data at gd[0] and all the game data for each threads at gd[1] to gd[$nb_proc]
struct thread_data * td;//gd contains the main game data at gd[0] and all the game data for each threads at gd[1] to gd[$nb_proc]

long long int max_possibility_score;
unsigned int accuracy = 1000;
int scoring_mode = 0;

int current_searching_floor = 0;
int current_searching_pos = 0;
int current_searching_pos_nb = 4;

int target_score = 0;
int score_max = 0;

unsigned long long int games_nbr = 0;
unsigned long long int starting_games_nbr = 0;
char name[100];
char name_suffix[100];
FILE *f = NULL;

int start_time = 0;
int checkpoint_time = 0;
unsigned long long int checkpoint_games_nbr = 0;

bool stop = false;
pthread_mutex_t save_mutex = NULL;
pthread_mutex_t new_game_mutex = NULL;

int nb_proc = 1;

unsigned long long int pow10(int x)
{
	unsigned long long int r = 1;
	for (int i = 0 ; i < x ; i ++)
		r *= 10;
	return r;
}

void format(unsigned long long int nbr)
{
	char str[100];
	int pos = 0;
	int exponent = 0;
	unsigned long long int i = nbr;

	while (i != 0)
	{
		i /= 10;
		exponent ++;
	}
	//printf("\nnumber = %llu, exponent = %d\n", nbr, exponent);
	for (; exponent > 0 ; exponent --)
	{
		i = (nbr / pow10(exponent-1)) - ((nbr / pow10(exponent)) * 10);
		str[pos++] = i + 48;
		//printf("%d\n", i);
		if ((exponent-1) % 3 == 0)
		{
			str[pos++] = ',';
		}
	}
	str[--pos] = '\0';
	printf("%s", str);
	//pause();
}

void format(int nbr)
{
	char str[100];
	int pos = 0;
	int exponent = 0;
	int i = nbr;

	while (i != 0)
	{
		i /= 10;
		exponent ++;
	}

	for (; exponent > 0 ; exponent --)
	{
		i = (nbr / pow10(exponent-1)) - ((nbr / pow10(exponent)) * 10);
		str[pos++] = i + 48;
		if ((exponent-1) % 3 == 0)
		{
			str[pos++] = ',';
		}
	}
	str[--pos] = '\0';
	printf("%s", str);
}

void save(bool display, int save_score = -1)
{
	pthread_mutex_lock(&save_mutex);
	FILE *solved_game = NULL;
	int ssc;

	if (save_score != -1)
	{
		ssc = save_score;
		solved_game = fopen("save.txt", "w+");
	}
	else
	{
		ssc = current_searching_floor+1;
		solved_game = fopen("quick_save.txt", "w+");
	}
	
	fprintf(solved_game, "games_nbr = %llu\nscore_max = %d\ndeep = %d\ntarget_score = %d\naccuracy = %d\nscoring_mode = %d\n", games_nbr, score_max, ssc, target_score, accuracy, scoring_mode);

	for (int x = 0 ; x < ssc ; x ++)
	{
		fprintf(solved_game, "\n%d|%d|%d|%d", gd[MAINGAME].searching_state[x][0], gd[MAINGAME].searching_state[x][1], gd[MAINGAME].searching_state[x][2], gd[MAINGAME].searching_state[x][3]);
	}
	rewind(solved_game);
	fclose(solved_game);
	if (display)
		printf("\nThe backup was properly done !\n");
	//pause();
	pthread_mutex_unlock(&save_mutex);
}

BOOL CtrlHandler( DWORD fdwCtrlType )
{
	switch( fdwCtrlType )
	{
		case CTRL_C_EVENT:
			save(false);
			stop = true;
			return TRUE;
		case CTRL_BREAK_EVENT:
			save(true);
			return TRUE;
		default:
			return FALSE;
	}
}

int add_line(struct line l, int game_no = -1)//Add the $l line to the $game_no game (if $game_no == -1 : add the $l line to all games)
{
	int i, x, y, line_no;

	if (game_no == -1)//add the $l line to all games
	{
		for (i = 0 ; i < nb_proc ; i ++)
			add_line(l, i);

		game_no = nb_proc;//Add $l line to the last game below
	}

	line_no = gd[game_no].line_no;

	gd[game_no].selected_lines[line_no].dir = l.dir;
	gd[game_no].selected_lines[line_no].pos = l.pos;
	gd[game_no].selected_lines[line_no].x = l.x;
	gd[game_no].selected_lines[line_no].y = l.y;

	//printf("line added to game %d : (%d,%d) %d %d\n", game_no, l.x, l.y, l.dir, l.pos);

	gd[game_no].line_no ++;
	gd[game_no].grid[l.x][l.y][8] = 1;
	if (l.x == gd[game_no].searching_range[0])//Increasing searching range if the added line is on the bounds
	{
		gd[game_no].searching_range[0] --;
	}
	else if (l.x == gd[game_no].searching_range[1])
	{
		gd[game_no].searching_range[1] ++;
	}
	if (l.y == gd[game_no].searching_range[2])
	{
		gd[game_no].searching_range[2] --;
	}
	else if (l.y == gd[game_no].searching_range[3])
	{
		gd[game_no].searching_range[3] ++;
	}

	if (l.dir == 1)//Add an horizontal line (-)
	{
		gd[game_no].grid[l.x - 2 + l.pos][l.y][3] = 1;
		for (i = (l.x - 1 + l.pos) ; i < (l.x + 2 + l.pos) ; i ++)
		{
			gd[game_no].grid[i][l.y][3] = 1;
			gd[game_no].grid[i][l.y][7] = 1;
		}
		gd[game_no].grid[l.x + 2 + l.pos][l.y][7] = 1;
	}
	else if (l.dir == 2)//Add a vertical line (|)
	{
		gd[game_no].grid[l.x][l.y - 2 + l.pos][5] = 1;
		for (i = (l.y - 1 + l.pos) ; i < (l.y + 2 + l.pos) ; i ++)
		{
			gd[game_no].grid[l.x][i][5] = 1;
			gd[game_no].grid[l.x][i][1] = 1;
		}
		gd[game_no].grid[l.x][l.y + 2 + l.pos][1] = 1;
	}
	else if (l.dir == 3)//Add an oblique line (/)
	{
		x = (l.x - 2 + l.pos);
		gd[game_no].grid[x][l.y + 2 - l.pos][2] = 1;
		x ++;
		for (y = (l.y + 1 - l.pos) ; y > (l.y - 2 - l.pos) ; y --)
		{
			gd[game_no].grid[x][y][2] = 1;
			gd[game_no].grid[x][y][6] = 1;
			x ++;
		}
		gd[game_no].grid[x][l.y - 2 - l.pos][6] = 1;
	}
	else if (l.dir == 4)//Add an oblique line (\)
	{
		x = (l.x - 2 + l.pos);
		gd[game_no].grid[x][l.y - 2 + l.pos][4] = 1;
		x ++;
		for (y = (l.y - 1 + l.pos) ; y < (l.y + 2 + l.pos) ; y ++)
		{
			gd[game_no].grid[x][y][4] = 1;
			gd[game_no].grid[x][y][0] = 1;
			x ++;
		}
		gd[game_no].grid[x][l.y + 2 + l.pos][0] = 1;
	}
	return 0;
}

int remove_line(int game_no = -1)//remove the last line to the $game_no game (if $game_no == -1 : remove the last line to all games)
{
	struct line l;
	int i, x, y;
	int line_no;

	if (game_no == -1)//remove the last line to all games
	{
		for (i = 0 ; i < nb_proc ; i ++)
			remove_line(i);

		game_no = nb_proc;//remove the last line to the last game below
	}

	gd[game_no].line_no --;
	line_no = gd[game_no].line_no;

	l.dir = gd[game_no].selected_lines[line_no].dir;
	l.pos = gd[game_no].selected_lines[line_no].pos;
	l.x = gd[game_no].selected_lines[line_no].x;
	l.y = gd[game_no].selected_lines[line_no].y;
	
	gd[game_no].selected_lines[line_no].x = 28;
	gd[game_no].selected_lines[line_no].y = 28;
	//printf("line removed to game %d : (%d,%d) %d %d\n", game_no, l.x, l.y, l.dir, l.pos);
	gd[game_no].grid[l.x][l.y][8] = 0;
	if (l.dir == 1)//Remove an horizontal line (-)
	{
		gd[game_no].grid[l.x - 2 + l.pos][l.y][3] = 0;
		for (i = (l.x - 1 + l.pos) ; i < (l.x + 2 + l.pos) ; i ++)
		{
			gd[game_no].grid[i][l.y][3] = 0;
			gd[game_no].grid[i][l.y][7] = 0;
		}
		gd[game_no].grid[l.x + 2 + l.pos][l.y][7] = 0;
	}
	else if (l.dir == 2)//Remove a vertical line (|)
	{
		gd[game_no].grid[l.x][l.y - 2 + l.pos][5] = 0;
		for (i = (l.y - 1 + l.pos) ; i < (l.y + 2 + l.pos) ; i ++)
		{
			gd[game_no].grid[l.x][i][5] = 0;
			gd[game_no].grid[l.x][i][1] = 0;
		}
		gd[game_no].grid[l.x][l.y + 2 + l.pos][1] = 0;
	}
	else if (l.dir == 3)//Remove an oblique line (/)
	{
		x = (l.x - 2 + l.pos);
		gd[game_no].grid[x][l.y + 2 - l.pos][2] = 0;
		x ++;
		for (y = (l.y + 1 - l.pos) ; y > (l.y - 2 - l.pos) ; y --)
		{
			gd[game_no].grid[x][y][2] = 0;
			gd[game_no].grid[x][y][6] = 0;
			x ++;
		}
		gd[game_no].grid[x][l.y - 2 - l.pos][6] = 0;
	}
	else if (l.dir == 4)//Remove an oblique line (\)
	{
		x = (l.x - 2 + l.pos);
		gd[game_no].grid[x][l.y - 2 + l.pos][4] = 0;
		x ++;
		for (y = (l.y - 1 + l.pos) ; y < (l.y + 2 + l.pos) ; y ++)
		{
			gd[game_no].grid[x][y][4] = 0;
			gd[game_no].grid[x][y][0] = 0;
			x ++;
		}
		gd[game_no].grid[x][l.y + 2 + l.pos][0] = 0;
	}
	return 0;
}

int possibilities_update(int game_no = -1)//update the possibilities of the $game_no game (if $game_no == -1 : update the possibilities of all games)
{
	int i;
	char x;
	char y;
	int no_pos = 0;
	bool add_pos = true;
	int floor;
	int gn = game_no;

	if (game_no == -1)//update the possibilities of all games (consist in updating the main game and only copy the possibilities found to the others)
		gn = MAINGAME;

	floor = gd[gn].score;
	//printf("updating pos game %d floor %d\n", gn, floor);
	for (y = gd[gn].searching_range[2] ; y <= gd[gn].searching_range[3] ; y ++)//We test all the search field
	{
		for (x = gd[gn].searching_range[0] ; x <= gd[gn].searching_range[1] ; x ++)
		{
			if (gd[gn].grid[x][y][USED] == 0)//Dots that are in the search field and which are empty are may host to one or more possibilities
			{
				//Test horizontal 2
				if ((gd[gn].grid[x + 1][y][USED] == 1) && (gd[gn].grid[x + 2][y][USED] == 1) && (gd[gn].grid[x + 3][y][USED] == 1) && (gd[gn].grid[x + 4][y][USED] == 1) && (gd[gn].grid[x + 1][y][RIGHT] == 0) && (gd[gn].grid[x + 2][y][RIGHT] == 0) && (gd[gn].grid[x + 3][y][RIGHT] == 0) && (gd[gn].grid[x + 2][y][LEFT] == 0) && (gd[gn].grid[x + 3][y][LEFT] == 0) && (gd[gn].grid[x + 4][y][LEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 1;
					gd[gn].possibilities[floor][no_pos].pos = 2;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test horizontal -2
				if ((gd[gn].grid[x - 1][y][USED] == 1) && (gd[gn].grid[x - 2][y][USED] == 1) && (gd[gn].grid[x - 3][y][USED] == 1) && (gd[gn].grid[x - 4][y][USED] == 1) && (gd[gn].grid[x - 1][y][LEFT] == 0) && (gd[gn].grid[x - 2][y][LEFT] == 0) && (gd[gn].grid[x - 3][y][LEFT] == 0) && (gd[gn].grid[x - 2][y][RIGHT] == 0) && (gd[gn].grid[x - 3][y][RIGHT] == 0) && (gd[gn].grid[x - 4][y][RIGHT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 1;
					gd[gn].possibilities[floor][no_pos].pos = -2;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test vertical 2
				if ((gd[gn].grid[x][y + 1][USED] == 1) && (gd[gn].grid[x][y + 2][USED] == 1) && (gd[gn].grid[x][y + 3][USED] == 1) && (gd[gn].grid[x][y + 4][USED] == 1) && (gd[gn].grid[x][y + 1][DOWN] == 0) && (gd[gn].grid[x][y + 2][DOWN] == 0) && (gd[gn].grid[x][y + 3][DOWN] == 0) && (gd[gn].grid[x][y + 2][UP] == 0) && (gd[gn].grid[x][y + 3][UP] == 0) && (gd[gn].grid[x][y + 4][UP] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 2;
					gd[gn].possibilities[floor][no_pos].pos = 2;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test vertical -2
				if ((gd[gn].grid[x][y - 1][USED] == 1) && (gd[gn].grid[x][y - 2][USED] == 1) && (gd[gn].grid[x][y - 3][USED] == 1) && (gd[gn].grid[x][y - 4][USED] == 1) && (gd[gn].grid[x][y - 2][DOWN] == 0) && (gd[gn].grid[x][y - 3][DOWN] == 0) && (gd[gn].grid[x][y - 4][DOWN] == 0) && (gd[gn].grid[x][y - 1][UP] == 0) && (gd[gn].grid[x][y - 2][UP] == 0) && (gd[gn].grid[x][y - 3][UP] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 2;
					gd[gn].possibilities[floor][no_pos].pos = -2;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test horizontal 1
				if ((gd[gn].grid[x - 1][y][USED] == 1) && (gd[gn].grid[x + 1][y][USED] == 1) && (gd[gn].grid[x + 2][y][USED] == 1) && (gd[gn].grid[x + 3][y][USED] == 1) && (gd[gn].grid[x + 1][y][RIGHT] == 0) && (gd[gn].grid[x + 2][y][RIGHT] == 0) && (gd[gn].grid[x + 2][y][LEFT] == 0) && (gd[gn].grid[x + 3][y][LEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 1;
					gd[gn].possibilities[floor][no_pos].pos = 1;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test horizontal -1
				if ((gd[gn].grid[x - 3][y][USED] == 1) && (gd[gn].grid[x - 2][y][USED] == 1) && (gd[gn].grid[x - 1][y][USED] == 1) && (gd[gn].grid[x + 1][y][USED] == 1) && (gd[gn].grid[x - 1][y][LEFT] == 0) && (gd[gn].grid[x - 2][y][LEFT] == 0) && (gd[gn].grid[x - 2][y][RIGHT] == 0) && (gd[gn].grid[x - 3][y][RIGHT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 1;
					gd[gn].possibilities[floor][no_pos].pos = -1;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test vertical 1
				if ((gd[gn].grid[x][y - 1][USED] == 1) && (gd[gn].grid[x][y + 1][USED] == 1) && (gd[gn].grid[x][y + 2][USED] == 1) && (gd[gn].grid[x][y + 3][USED] == 1) && (gd[gn].grid[x][y + 1][DOWN] == 0) && (gd[gn].grid[x][y + 2][DOWN] == 0) && (gd[gn].grid[x][y + 2][UP] == 0) && (gd[gn].grid[x][y + 3][UP] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 2;
					gd[gn].possibilities[floor][no_pos].pos = 1;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test vertical -1
				if ((gd[gn].grid[x][y + 1][USED] == 1) && (gd[gn].grid[x][y - 1][USED] == 1)&& (gd[gn].grid[x][y - 2][USED] == 1) && (gd[gn].grid[x][y - 3][USED] == 1) && (gd[gn].grid[x][y - 1][UP] == 0) && (gd[gn].grid[x][y - 2][UP] == 0) && (gd[gn].grid[x][y - 2][DOWN] == 0) && (gd[gn].grid[x][y - 3][DOWN] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 2;
					gd[gn].possibilities[floor][no_pos].pos = -1;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test horizontal 0
				if ((gd[gn].grid[x - 2][y][USED] == 1) && (gd[gn].grid[x - 1][y][USED] == 1) && (gd[gn].grid[x + 1][y][USED] == 1) && (gd[gn].grid[x + 2][y][USED] == 1) && (gd[gn].grid[x - 2][y][RIGHT] == 0) && (gd[gn].grid[x - 1][y][LEFT] == 0) && (gd[gn].grid[x + 1][y][RIGHT] == 0) && (gd[gn].grid[x + 2][y][LEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 1;
					gd[gn].possibilities[floor][no_pos].pos = 0;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test vertical 0
				if ((gd[gn].grid[x][y - 2][USED] == 1) && (gd[gn].grid[x][y - 1][USED] == 1) && (gd[gn].grid[x][y + 1][USED] == 1) && (gd[gn].grid[x][y + 2][USED] == 1) && (gd[gn].grid[x][y - 2][DOWN] == 0) && (gd[gn].grid[x][y - 1][UP] == 0) && (gd[gn].grid[x][y + 1][DOWN] == 0) && (gd[gn].grid[x][y + 2][UP] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 2;
					gd[gn].possibilities[floor][no_pos].pos = 0;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test oblique1 2
				if ((gd[gn].grid[x + 1][y - 1][USED] == 1) && (gd[gn].grid[x + 2][y - 2][USED] == 1) && (gd[gn].grid[x + 3][y - 3][USED] == 1) && (gd[gn].grid[x + 4][y - 4][USED] == 1) && (gd[gn].grid[x + 1][y - 1][UPRIGHT] == 0) && (gd[gn].grid[x + 2][y - 2][UPRIGHT] == 0) && (gd[gn].grid[x + 3][y - 3][UPRIGHT] == 0) && (gd[gn].grid[x + 2][y - 2][DOWNLEFT] == 0) && (gd[gn].grid[x + 3][y - 3][DOWNLEFT] == 0) && (gd[gn].grid[x + 4][y - 4][DOWNLEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 3;
					gd[gn].possibilities[floor][no_pos].pos = 2;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique1 -2
				if ((gd[gn].grid[x - 1][y + 1][USED] == 1) && (gd[gn].grid[x - 2][y + 2][USED] == 1) && (gd[gn].grid[x - 3][y + 3][USED] == 1) && (gd[gn].grid[x - 4][y + 4][USED] == 1) && (gd[gn].grid[x - 1][y + 1][DOWNLEFT] == 0) && (gd[gn].grid[x - 2][y + 2][DOWNLEFT] == 0) && (gd[gn].grid[x - 3][y + 3][DOWNLEFT] == 0) && (gd[gn].grid[x - 2][y + 2][UPRIGHT] == 0) && (gd[gn].grid[x - 3][y + 3][UPRIGHT] == 0) && (gd[gn].grid[x - 4][y + 4][UPRIGHT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 3;
					gd[gn].possibilities[floor][no_pos].pos = -2;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique1 1
				if ((gd[gn].grid[x - 1][y + 1][USED] == 1) && (gd[gn].grid[x + 1][y - 1][USED] == 1) && (gd[gn].grid[x + 2][y - 2][USED] == 1) && (gd[gn].grid[x + 3][y - 3][USED] == 1) && (gd[gn].grid[x + 1][y - 1][UPRIGHT] == 0) && (gd[gn].grid[x + 2][y - 2][UPRIGHT] == 0) && (gd[gn].grid[x + 2][y - 2][DOWNLEFT] == 0) && (gd[gn].grid[x + 3][y - 3][DOWNLEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 3;
					gd[gn].possibilities[floor][no_pos].pos = 1;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique1 -1
				if ((gd[gn].grid[x - 3][y + 3][USED] == 1) && (gd[gn].grid[x - 2][y + 2][USED] == 1) && (gd[gn].grid[x - 1][y + 1][USED] == 1) && (gd[gn].grid[x + 1][y - 1][USED] == 1) && (gd[gn].grid[x - 1][y + 1][DOWNLEFT] == 0) && (gd[gn].grid[x - 2][y + 2][DOWNLEFT] == 0) && (gd[gn].grid[x - 2][y + 2][UPRIGHT] == 0) && (gd[gn].grid[x - 3][y + 3][UPRIGHT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 3;
					gd[gn].possibilities[floor][no_pos].pos = -1;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique1 0
				if ((gd[gn].grid[x - 2][y + 2][USED] == 1) && (gd[gn].grid[x - 1][y + 1][USED] == 1) && (gd[gn].grid[x + 1][y - 1][USED] == 1) && (gd[gn].grid[x + 2][y - 2][USED] == 1) && (gd[gn].grid[x - 2][y + 2][UPRIGHT] == 0) && (gd[gn].grid[x - 1][y + 1][DOWNLEFT] == 0) && (gd[gn].grid[x + 1][y - 1][UPRIGHT] == 0) && (gd[gn].grid[x + 2][y - 2][DOWNLEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 3;
					gd[gn].possibilities[floor][no_pos].pos = 0;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test oblique2 2
				if ((gd[gn].grid[x + 1][y + 1][USED] == 1) && (gd[gn].grid[x + 2][y + 2][USED] == 1) && (gd[gn].grid[x + 3][y + 3][USED] == 1) && (gd[gn].grid[x + 4][y + 4][USED] == 1) && (gd[gn].grid[x + 1][y + 1][DOWNRIGHT] == 0) && (gd[gn].grid[x + 2][y + 2][DOWNRIGHT] == 0) && (gd[gn].grid[x + 3][y + 3][DOWNRIGHT] == 0) && (gd[gn].grid[x + 2][y + 2][UPLEFT] == 0) && (gd[gn].grid[x + 3][y + 3][UPLEFT] == 0) && (gd[gn].grid[x + 4][y + 4][UPLEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 4;
					gd[gn].possibilities[floor][no_pos].pos = 2;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique2 -2
				if ((gd[gn].grid[x - 1][y - 1][USED] == 1) && (gd[gn].grid[x - 2][y - 2][USED] == 1) && (gd[gn].grid[x - 3][y - 3][USED] == 1) && (gd[gn].grid[x - 4][y - 4][USED] == 1)  && (gd[gn].grid[x - 1][y - 1][UPLEFT] == 0) && (gd[gn].grid[x - 2][y - 2][UPLEFT] == 0) && (gd[gn].grid[x - 3][y - 3][UPLEFT] == 0) && (gd[gn].grid[x - 2][y - 2][DOWNRIGHT] == 0) && (gd[gn].grid[x - 3][y - 3][DOWNRIGHT] == 0) && (gd[gn].grid[x - 4][y - 4][DOWNRIGHT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 4;
					gd[gn].possibilities[floor][no_pos].pos = -2;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique2 1
				if ((gd[gn].grid[x - 1][y - 1][USED] == 1) && (gd[gn].grid[x + 1][y + 1][USED] == 1) && (gd[gn].grid[x + 2][y + 2][USED] == 1) && (gd[gn].grid[x + 3][y + 3][USED] == 1) && (gd[gn].grid[x + 1][y + 1][DOWNRIGHT] == 0) && (gd[gn].grid[x + 2][y + 2][DOWNRIGHT] == 0) && (gd[gn].grid[x + 2][y + 2][UPLEFT] == 0) && (gd[gn].grid[x + 3][y + 3][UPLEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 4;
					gd[gn].possibilities[floor][no_pos].pos = 1;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique2 -1
				if ((gd[gn].grid[x - 3][y - 3][USED] == 1) && (gd[gn].grid[x - 2][y - 2][USED] == 1) && (gd[gn].grid[x - 1][y - 1][USED] == 1) && (gd[gn].grid[x + 1][y + 1][USED] == 1) && (gd[gn].grid[x - 3][y - 3][DOWNRIGHT] == 0) && (gd[gn].grid[x - 2][y - 2][DOWNRIGHT] == 0) && (gd[gn].grid[x - 2][y - 2][UPLEFT] == 0) && (gd[gn].grid[x - 1][y - 1][UPLEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 4;
					gd[gn].possibilities[floor][no_pos].pos = -1;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique2 0
				if ((gd[gn].grid[x - 2][y - 2][USED] == 1) && (gd[gn].grid[x - 1][y - 1][USED] == 1) && (gd[gn].grid[x + 1][y + 1][USED] == 1) && (gd[gn].grid[x + 2][y + 2][USED] == 1) && (gd[gn].grid[x - 2][y - 2][DOWNRIGHT] == 0) && (gd[gn].grid[x - 1][y - 1][UPLEFT] == 0) && (gd[gn].grid[x + 1][y + 1][DOWNRIGHT] == 0) && (gd[gn].grid[x + 2][y + 2][UPLEFT] == 0))
				{
					gd[gn].possibilities[floor][no_pos].dir = 4;
					gd[gn].possibilities[floor][no_pos].pos = 0;
					gd[gn].possibilities[floor][no_pos].x = x;
					gd[gn].possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
			}
		}
	}

	gd[gn].possibilities[floor][no_pos].x = 28;//End list mark
	gd[gn].possibilities[floor][no_pos].y = 28;

	if (game_no == -1)//Copying the possibility list for all the games
	{
		for (i = 0 ; i <= no_pos ; i ++)
		{
			for (gn = 1 ; gn <= nb_proc ; gn ++)
			{
				gd[gn].possibilities[floor][i].dir = gd[MAINGAME].possibilities[floor][i].dir;
				gd[gn].possibilities[floor][i].pos = gd[MAINGAME].possibilities[floor][i].pos;
				gd[gn].possibilities[floor][i].x = gd[MAINGAME].possibilities[floor][i].x;
				gd[gn].possibilities[floor][i].y = gd[MAINGAME].possibilities[floor][i].y;
			}
		}
	}

	return no_pos;//We return the number of possibilities
}

void new_game_found(int game_no)//save the new game found if it is better than all the games found before
{
	games_nbr ++;
	if (gd[game_no].score > score_max)//If the score becomes higher than the last best score, then the grid is saved in an file
	{
		score_max = gd[game_no].score;
		printf("\r                                                                               \rNb games : ");
		format(games_nbr);
		printf(", A new best game was found, score : %d\n", score_max);

		char save_location[248];
		sprintf_s(save_location, "games");
		CreateDirectoryA((LPCSTR)&save_location, NULL);

		sprintf(name, "games/game_");
		sprintf(name_suffix, "%d", score_max);
		strcat(name, name_suffix);
		strcat(name, ".txt");
		f = fopen(name, "w+");
		fprintf(f, "# JEC2000's game\n#\n");
		fprintf(f, "# Score : %d\n(28,28)\n", score_max);
		int i = 0;
		while ((gd[game_no].selected_lines[i].x != 28) || (gd[game_no].selected_lines[i].y != 28))
		{
			if (gd[game_no].selected_lines[i].dir == 1)
			{
				fprintf(f, "(%d,%d) - %d\n", gd[game_no].selected_lines[i].x, gd[game_no].selected_lines[i].y, gd[game_no].selected_lines[i].pos);
			}
			else if (gd[game_no].selected_lines[i].dir == 2)
			{
				fprintf(f, "(%d,%d) | %d\n", gd[game_no].selected_lines[i].x, gd[game_no].selected_lines[i].y, gd[game_no].selected_lines[i].pos);
			}
			else if (gd[game_no].selected_lines[i].dir == 3)
			{
				fprintf(f, "(%d,%d) / %d\n", gd[game_no].selected_lines[i].x, gd[game_no].selected_lines[i].y, gd[game_no].selected_lines[i].pos);
			}
			else if (gd[game_no].selected_lines[i].dir == 4)
			{
				fprintf(f, "(%d,%d) \\ %d\n", gd[game_no].selected_lines[i].x, gd[game_no].selected_lines[i].y, gd[game_no].selected_lines[i].pos);
			}
			i ++;
		}
		rewind(f);
		fclose(f);
		save(false);

		if (gd[game_no].score > target_score)
			stop = true;
	}
	if ((GetTickCount() - checkpoint_time) >= 1000)//Shows every seconds the number of completed games and some info to the user
	{
		printf("\r                                                                               \rTested : ");
		format(games_nbr);
		printf(" floor %d (%d/%d) ", current_searching_floor+1, current_searching_pos+1, current_searching_pos_nb);
		if ((GetTickCount() - start_time) >= 1000)//We avoids a division by zero...
		{
			printf("speed (avg) : ");
			format((games_nbr - checkpoint_games_nbr) / (int)((GetTickCount() - checkpoint_time) / 1000));
			printf(" (");
			format((games_nbr - starting_games_nbr) / (int)((GetTickCount() - start_time) / 1000));
			printf(") games/sec");
		}
		checkpoint_games_nbr = games_nbr;
		checkpoint_time = GetTickCount();
	}
}

void * random_tests(void* data)//Second part of the algorithm, we do $accuracy random tests on the $no possibility 
{
	int no_thread = (int)data + 1;
	int no = td[no_thread-1].no_pos;

	gd[no_thread].score++;

	int nb_pos;
	struct line l = gd[MAINGAME].possibilities[gd[no_thread].score - 1][no];
	int total_score = 0;

	//printf("Thread %d : score : %d, line %d,%d,%d,%d\n", no_thread, l.dir, l.pos, l.x, l.y);
	if (stop)//To stop search while we are saving...
	{
		td[no_thread-1].score = SAVEREQUIRED;
		pthread_exit(0);
		return 0;
	}
	
	add_line(l, no_thread);//We add to the no_thread game the line l
	nb_pos = possibilities_update(no_thread);//We must update possibilities after adding this line.

	if (nb_pos == 0)//If there is no more possibilities, then we've just completed a game
	{
		pthread_mutex_lock(&new_game_mutex);//A new game is found, if we are thread 1 we have to update the display. Other threads are only allowed to update the $game_nbr and save a best game
		if ((no_thread == 1) || (gd[no_thread].score > score_max))
			new_game_found(no_thread);
		else
			games_nbr ++;
		pthread_mutex_unlock(&new_game_mutex);
		if (gd[no_thread].score > target_score)//If we have exceeded the maximum score wanted by the user, then we exit the recursive search
		{
			td[no_thread-1].score = BESTSCOREFOUND;
			pthread_exit(0);
			return 0;
		}
		else//Otherwise we remove the line that was added at the beginning of the function and we descend from one floor in the tree
		{
			remove_line(no_thread);
			gd[no_thread].score --;
			td[no_thread-1].score = 0;
			pthread_exit(0);
			return 0;
		}
	}

	int score_temp = gd[no_thread].score;//We save the score of this level
	int nb_pos_temp;
	int no_rand_pos;

	for (int nbt = 0 ; nbt <= (accuracy / nb_proc) ; nbt ++)
	{
		if (no_thread == 1)
			srand (time(NULL) + nbt);
		no_rand_pos = rand() % nb_pos;//We choose the possibility
		
		if (stop)//To stop search while we are saving...
		{
			td[no_thread-1].score = SAVEREQUIRED;
			pthread_exit(0);
			return 0;
		}
		//printf("Thread %d, testing %d/%d\n", no_thread, nbt, (accuracy / nb_proc));
		//pause();
		do//Testing one random game from the floor we are testing in the main game thread
		{
			gd[no_thread].score ++;
			add_line(gd[no_thread].possibilities[gd[no_thread].score - 1][no_rand_pos], no_thread);//We add to the game the corresponding line to the randomly choosen possibility
			nb_pos_temp = possibilities_update(no_thread);//We must update possibilities after adding this line.
			//printf("Thread %d, nb_pos %d\n", no_thread, nb_pos_temp);
			//pause();
			if (nb_pos_temp == 0)//If there is no more possibilities, then we've just completed a game
			{
				if (scoring_mode == 0)//If scoring mode is the average score
					total_score += gd[no_thread].score;//We add the new score to the total score of the possibility
				else if (gd[no_thread].score > total_score)//If scoring mode is the maximum score
					total_score = gd[no_thread].score;//We store the new score in the max score of the possibility

				pthread_mutex_lock(&new_game_mutex);//A new game is found, if we are thread 1 we have to update the display. Other threads are only allowed to update the $game_nbr and save a best game
				if ((no_thread == 1) || (gd[no_thread].score > score_max))
					new_game_found(no_thread);
				else
					games_nbr ++;
				pthread_mutex_unlock(&new_game_mutex);

				if (gd[no_thread].score > target_score)//If we have exceeded the maximum score wanted by the user, then we exit the recursive search
				{
					td[no_thread-1].score = BESTSCOREFOUND;
					pthread_exit(0);
					return 0;
				}
				else//Otherwise we remove all the lines that were added
				{
					for (; gd[no_thread].score > score_temp ; gd[no_thread].score --)
					{
						remove_line(no_thread);
					}
					break;
				}
			}
			else
			{
				no_rand_pos = rand() % nb_pos_temp;//We choose the possibility of the next floor
			}
		}
		while (true);//While there is at least one possibility, we continue to add them.
	}

	
	remove_line(no_thread);
	gd[no_thread].score --;
	td[no_thread-1].score = total_score;
	pthread_exit(0);
	return 0;
}

int resolution(int no)//first part of the algorithm, we do the research for each possibility
{
	gd[MAINGAME].score++;
	int i, x, nb_pos, result;
	struct line l = gd[MAINGAME].possibilities[gd[MAINGAME].score - 1][no];
	int total_score = 0;
	int no_thread;

	save(false);

	if (stop)
		return SAVEREQUIRED;
	
	add_line(l);//We add to the game the corresponding line to the possibility "no"
	nb_pos = possibilities_update();//We must update possibilities after adding this line.

	if (nb_pos == 0)//If there is no more possibilities, then we've just completed a game
	{
		new_game_found(MAINGAME);//A new game is found.
		if (gd[MAINGAME].score > target_score)//If we have exceeded the maximum score wanted by the user, then we exit the recursive search
		{
			//printf("exit 1\n");
			return BESTSCOREFOUND;
		}
		else//Otherwise we remove the line that was added at the beginning of the function and we descend from one floor in the tree
		{
			//printf("exit 2\n");
			remove_line();
			gd[MAINGAME].score --;
			return 0;
		}
	}
	if ((gd[MAINGAME].searching_state[gd[MAINGAME].score][0] > 0) && (gd[MAINGAME].searching_state[gd[MAINGAME].score][0] <= nb_pos))//We must restore the progress of research after a backup
		x = gd[MAINGAME].searching_state[gd[MAINGAME].score][0] - 1;//So we continue where we stopped, with the possibility contained in the searching_state table (indexed between [0 and n-1] here and between [1 and n] for the backup therefore we subtract 1)
	else//Otherwise we starts searching from the first possibility (index 0)
		x = -1;

	gd[MAINGAME].searching_state[gd[MAINGAME].score][1] = nb_pos;//We updates the total number of possibilities of that floor

	current_searching_floor = gd[MAINGAME].score;
	current_searching_pos_nb = nb_pos;
	int temp_score;
	int best_pos = gd[MAINGAME].searching_state[gd[MAINGAME].score][2]-1;
	max_possibility_score = gd[MAINGAME].searching_state[gd[MAINGAME].score][3];

	if ((x == -1) || (best_pos != x))//We were testing the possibility x of n_pos and we found the best possibility at best_pos with a score of max_possibility_score
	{
		if (x == -1)
		{
			x = 0;
			best_pos = -1;
			max_possibility_score = -1;
		}
		//printf("\nTesting %d possibilities at floor %d\nstate : %d %d %d %d\n", nb_pos, gd[MAINGAME].score+1, gd[MAINGAME].searching_state[gd[MAINGAME].score][0]-1, gd[MAINGAME].searching_state[gd[MAINGAME].score][1], gd[MAINGAME].searching_state[gd[MAINGAME].score][2]-1, gd[MAINGAME].searching_state[gd[MAINGAME].score][3]);
		for (i = x ; i < nb_pos ; i ++)
		{
			current_searching_pos = i;
			gd[MAINGAME].searching_state[gd[MAINGAME].score][0] = i+1;
			for(no_thread = 0 ; no_thread < nb_proc ; no_thread ++)
			{
				td[no_thread].no_pos = i;
				gd[no_thread+1].score = gd[MAINGAME].score;
				pthread_create(&td[no_thread].thread, NULL, random_tests, (void *)no_thread);//We test randomly the score of each possibility
			}
			temp_score = 0;
			for(no_thread = 0 ; no_thread < nb_proc ; no_thread ++)
			{
				pthread_join(td[no_thread].thread, NULL);

				if (scoring_mode == 0)//If scoring mode is the average score
					temp_score += td[no_thread].score;//We add the new score to the total score of the possibility
				else if (td[no_thread].score > temp_score)//If scoring mode is the maximum score
					temp_score = td[no_thread].score;//We store the new score in the max score of the possibility
			}
			//printf("\nTested pos %d/%d : score : %d, (global score : %d)", i+1, nb_pos, temp_score, score);
			if (temp_score > max_possibility_score)
			{
				max_possibility_score = temp_score;
				best_pos = i;
				gd[MAINGAME].searching_state[gd[MAINGAME].score][2] = i+1;
				gd[MAINGAME].searching_state[gd[MAINGAME].score][3] = temp_score;
				//printf(" MAX SCORED !");
			}
			else if (stop)//If we found a game with a score greater or equal than requested or if the backup has been requested in an upper floor then we quit
			{
				gd[MAINGAME].score --;
				return SAVEREQUIRED;
			}
			save(false);
			//printf("\n");
		}
		//pause();
	}

	if (best_pos == -1)
		return 0;//We stop if there are no more possibilities we don't actually need this because if we are here there are at least 1 possibility

	gd[MAINGAME].searching_state[gd[MAINGAME].score][0] = best_pos + 1;//We increment the state in searching_state to save it

	result = resolution(best_pos);//We go up from one floor in the tree with the possibility i and we increment the score

	if (result == BESTSCOREFOUND)//If we found a game with a score greater or equal than requested, then we descend of a floor, else we continue to try the other possibilities
		return BESTSCOREFOUND;
	else if (result == SAVEREQUIRED)//Backup has been requested in an upper floor
	{
		gd[MAINGAME].score --;
		return SAVEREQUIRED;
	}
	
	gd[MAINGAME].searching_state[gd[MAINGAME].score][0] = -1;
	remove_line();
	gd[MAINGAME].score --;
	return total_score;
}


int main(int argc, char* argv[])
{
	int i, x, y, a, b, c, d, result, nb_pos;
	FILE *solved_game = NULL;
	srand (time (NULL));
	struct _SYSTEM_INFO sys_infos;
	GetSystemInfo(&sys_infos);
	nb_proc = sys_infos.dwNumberOfProcessors;

	//printf("ProcessorArchitecture : %d\nPageSize : %d\nActiveProcessorMask : %d\nNumberOfProcessors : %d\nProcessorType : %d\nAllocationGranularity : %d\nProcessorLevel : %d\nProcessorRevision : %d\n", sys_infos.wProcessorArchitecture, sys_infos.dwPageSize, sys_infos.dwActiveProcessorMask, sys_infos.dwNumberOfProcessors, sys_infos.dwProcessorType, sys_infos.dwAllocationGranularity, sys_infos.wProcessorLevel, sys_infos.wProcessorRevision);
	
	gd = (struct game_data*) calloc(nb_proc+1, sizeof(struct game_data));//Allocating the games data
	td = (struct thread_data*) calloc(nb_proc, sizeof(struct thread_data));//Allocating the threads data

	for (i = 0 ; i < 1000 ; i ++)//Initialising the searching state table of the main game data
	{
		gd[MAINGAME].searching_state[i][0] = -1;
		gd[MAINGAME].searching_state[i][1] = -1;
		gd[MAINGAME].searching_state[i][2] = 0;
		gd[MAINGAME].searching_state[i][3] = 0;
	}
	f = fopen("save.txt", "r+");
	if (f != NULL)//Loading the saved search
	{
		fscanf(f, "games_nbr = %llu\n", &games_nbr);
		starting_games_nbr = games_nbr;
		fscanf(f, "score_max = %d\n", &score_max);
		fscanf(f, "deep = %d\n", &x);
		fscanf(f, "target_score = %d\n", &target_score);
		fscanf(f, "accuracy = %d\n", &accuracy);
		fscanf(f, "scoring_mode = %d\n", &scoring_mode);
		for (i = 0 ; i < x ; i ++)
		{
			fscanf(f, "\n%d|%d|%d|%d", &a, &b, &c, &d);
			gd[MAINGAME].searching_state[i][0] = a;
			gd[MAINGAME].searching_state[i][1] = b;
			gd[MAINGAME].searching_state[i][2] = c;
			gd[MAINGAME].searching_state[i][3] = d;
			//printf("\n%d|%d|%d|%d", gd[MAINGAME].searching_state[i][0], gd[MAINGAME].searching_state[i][1], gd[MAINGAME].searching_state[i][2], gd[MAINGAME].searching_state[i][3]);
			if (a <= 0 || b <= 0 || a > b || b > CHAR_MAX || c < 0 || d < 0 || c > a)
			{
				printf("A reading error has occured.\nHave you modified the save.txt file ?\nProgram will now stop.\n");
				fclose(f);
				pause();
				return 0;
			}
			//printf("searching_state[%d] = [%d,%d]\n", i, searching_state[i][0], searching_state[i][1]);
		}
		//printf("searching_state[%d] = [%d,%d]\n", i, searching_state[i][0], searching_state[i][1]);
		fclose(f);
		printf("Morpion Solitaire by JEC2000\n\nSearch parameters :\nTarget score : %d\n", target_score);
		games_nbr --;
		printf("Number of games tested : ");
		format(games_nbr);
		printf("\nMaximum score reached : %d\n", score_max);

		printf("Accuracy : ");
		format((int)accuracy);
		printf(" random tests (");
		format((int)(accuracy / nb_proc));
		printf(" / thread, %d threads)\n", nb_proc);
		if (scoring_mode == 0)
		{
			printf("Scoring possibility mode : average score\n");
		}
		else
		{
			printf("Scoring possibility mode : max score\n");
		}
	}
	else
	{
		printf("Morpion Solitaire by JEC2000\n\nEnter a target score (best known 178) : ");
		scanf("%d", &target_score);
		fflush(stdin);
		printf("\nEnter the number of random tests (>1) : ");
		scanf("%d", &accuracy);
		fflush(stdin);
		printf("\nEnter the scoring possibility mode (0 : average score, 1 : max score) : ");
		scanf("%d", &scoring_mode);
		fflush(stdin);
	}
	if (accuracy < nb_proc)
		accuracy = nb_proc;
	
	printf("\nPress CTRL+C to save and quit\n");
	printf("Press CTRL+BREAK to do a quick save and continue\n\n");
	//pause();

	HWND hConsole = GetConsoleWindow();
	HMENU hMenu = GetSystemMenu(hConsole, FALSE);
	DeleteMenu(hMenu, SC_CLOSE, MF_BYCOMMAND);//Disable the close cross button of the window

	SetConsoleCtrlHandler((PHANDLER_ROUTINE) CtrlHandler, TRUE);//Launches CtrlHandler function when receiving the signal CTRL+C or CTRL+BREAK
	pthread_mutex_init(&save_mutex, NULL);
	pthread_mutex_init(&new_game_mutex, NULL);

	for (int game = 0 ; game <= nb_proc ; game++)//Initialising game data for each threads
	{
		for (x = 0 ; x < 60 ; x ++)//initialising the game grid
		{
			for (y = 0 ; y < 60 ; y ++)
			{
				for (i = 0 ; i < 9 ; i ++)
				{
					gd[game].grid[x][y][i] = 0;
				}
			}
		}

		for (i = 25 ; i < 29 ; i ++)//initialising the game grid
		{
			gd[game].grid[i][28][8] = 1;
			gd[game].grid[i][31][8] = 1;
			gd[game].grid[i+3][25][8] = 1;
			gd[game].grid[i+3][34][8] = 1;
			gd[game].grid[i+6][28][8] = 1;
			gd[game].grid[i+6][31][8] = 1;

			gd[game].grid[28][i][8] = 1;
			gd[game].grid[31][i][8] = 1;
			gd[game].grid[25][i+3][8] = 1;
			gd[game].grid[34][i+3][8] = 1;
			gd[game].grid[28][i+6][8] = 1;
			gd[game].grid[31][i+6][8] = 1;
		}

		for (i = 0 ; i < 1000 ; i ++)//initialising the selected_lines table
		{
			gd[game].selected_lines[i].dir = 0;
			gd[game].selected_lines[i].pos = 0;
			gd[game].selected_lines[i].x = 28;
			gd[game].selected_lines[i].y = 28;
		}
		gd[game].searching_range[0] = 24;//Initialising the searching range table
		gd[game].searching_range[1] = 35;
		gd[game].searching_range[2] = 24;
		gd[game].searching_range[3] = 35;
		gd[game].score = 0;//Initialising the score
	}
	
	possibilities_update();
	nb_pos = 4;
	int root_pos[4] = {0,2,5,9};//We have only 4 true possibilities in the root because the others can be obtained by a symetry or a rotation of the game
	int no_thread;

	if ((gd[MAINGAME].searching_state[gd[MAINGAME].score][0] > 0) && (gd[MAINGAME].searching_state[gd[MAINGAME].score][0] <= nb_pos))//We must restore the progress of research after a backup
		x = gd[MAINGAME].searching_state[gd[MAINGAME].score][0] - 1;//So we continue where we stopped, with the possibility contained in the searching_state table (indexed between [0 and n-1] here and between [1 and n] for the backup therefore we subtract 1)
	else//Otherwise we starts searching from the first possibility (index 0)
		x = -1;

	gd[MAINGAME].searching_state[0][1] = nb_pos;
	start_time = GetTickCount();//We set the start time for displaying the speed of the algorithm
	checkpoint_games_nbr = starting_games_nbr;
	
	int temp_score;
	int best_pos = gd[MAINGAME].searching_state[0][2]-1;
	max_possibility_score = gd[MAINGAME].searching_state[0][3];
	//printf("\nTesting %d possibilities at floor %d\n", nb_pos, gd[MAINGAME].score);

	if ((x == -1) || (best_pos != x))//We were testing the possibility x of n_pos and we found the best possibility at best_pos with a score of max_possibility_score
	{
		if (x == -1)
		{
			x = 0;
			best_pos = -1;
			max_possibility_score = -1;
		}
		for (i = x ; i < nb_pos ; i ++)
		{
			//printf("\nTesting pos %d/%d\n", i+1, nb_pos);
			current_searching_pos = i;
			gd[MAINGAME].searching_state[gd[MAINGAME].score][0] = i+1;
			for(no_thread = 0 ; no_thread < nb_proc ; no_thread ++)
			{
				td[no_thread].no_pos = root_pos[i];
				gd[no_thread+1].score = gd[MAINGAME].score;
				pthread_create(&td[no_thread].thread, NULL, random_tests, (void *)no_thread);//We test randomly the score of each possibility
				//printf("\nCreated thread %d/%d\n", no_thread+1, nb_proc);
			}
			temp_score = 0;
			for(no_thread = 0 ; no_thread < nb_proc ; no_thread ++)
			{
				pthread_join(td[no_thread].thread, NULL);
				//printf("\nFinished thread %d/%d : score : %d\n", no_thread+1, nb_proc, td[no_thread].score);
				if (scoring_mode == 0)//If scoring mode is the average score
					temp_score += td[no_thread].score;//We add the new score to the total score of the possibility
				else if (td[no_thread].score > temp_score)//If scoring mode is the maximum score
					temp_score = td[no_thread].score;//We store the new score in the max score of the possibility
			}
			//printf("\nTested pos %d/%d : score : %d, (global score : %d)\n", i+1, nb_pos, temp_score, gd[MAINGAME].score);
			if (temp_score > max_possibility_score)
			{
				max_possibility_score = temp_score;
				best_pos = i;
				gd[MAINGAME].searching_state[gd[MAINGAME].score][2] = i+1;
				gd[MAINGAME].searching_state[gd[MAINGAME].score][3] = temp_score;
				//printf(" MAX SCORED !");
			}
			else if (temp_score == BESTSCOREFOUND)//If we found a game with a score greater or equal than requested, then we descend of a floor, else we continue to try the other possibilities
			{
				result = BESTSCOREFOUND;
				break;
			}
			else if (temp_score == SAVEREQUIRED)//Backup has been requested in an upper floor
			{
				gd[MAINGAME].score --;
				result = SAVEREQUIRED;
				break;
			}
			//printf("\n");
		}
	}

	if ((result != BESTSCOREFOUND) && (result != SAVEREQUIRED))
	{
		//printf("\nbest pos : %d\n", best_pos+1);
		gd[MAINGAME].searching_state[0][0] = best_pos + 1;//We increment the state in searching_state to save it
		result = resolution(root_pos[best_pos]);//We go up from one floor in the tree with the possibility root_pos[i] and we increment the score
	}

	if ((result != BESTSCOREFOUND) && (result != SAVEREQUIRED))
	{
		printf("\nSearch terminated !\nNo games were found with a score greater or equal than requested !\n");//Algorithm finished without finding any games with a score greater than or equal than requested
		result = -1;
	}
	else
	{
		//saving searching state
	
		i = 0;
		while (gd[MAINGAME].searching_state[i][0] != -1)
		{
			i ++;
		}

		save(true, i);
	}
	
	if (result == BESTSCOREFOUND)//We found a game with a score greater or equal to the required score, we save it
	{
		i = 0;
		solved_game = fopen("solved_game.txt", "w+");
		fprintf(solved_game, "# JEC2000's game\n#\n");
		fprintf(solved_game, "# Score : %d\n(28,28)\n", gd[MAINGAME].score);

		while ((gd[MAINGAME].selected_lines[i].x != 28) || (gd[MAINGAME].selected_lines[i].y != 28))
		{
			if (gd[MAINGAME].selected_lines[i].dir == 1)
			{
				fprintf(solved_game, "(%d,%d) - %d\n", gd[MAINGAME].selected_lines[i].x, gd[MAINGAME].selected_lines[i].y, gd[MAINGAME].selected_lines[i].pos);
			}
			else if (gd[MAINGAME].selected_lines[i].dir == 2)
			{
				fprintf(solved_game, "(%d,%d) | %d\n", gd[MAINGAME].selected_lines[i].x, gd[MAINGAME].selected_lines[i].y, gd[MAINGAME].selected_lines[i].pos);
			}
			else if (gd[MAINGAME].selected_lines[i].dir == 3)
			{
				fprintf(solved_game, "(%d,%d) / %d\n", gd[MAINGAME].selected_lines[i].x, gd[MAINGAME].selected_lines[i].y, gd[MAINGAME].selected_lines[i].pos);
			}
			else if (gd[MAINGAME].selected_lines[i].dir == 4)
			{
				fprintf(solved_game, "(%d,%d) \\ %d\n", gd[MAINGAME].selected_lines[i].x, gd[MAINGAME].selected_lines[i].y, gd[MAINGAME].selected_lines[i].pos);
			}
			i ++;
		}
		printf("A new game was found after %d games :\nScore : %d\n", games_nbr, gd[MAINGAME].score);
		rewind(solved_game);
		fclose(solved_game);
	}
	pause();
	pthread_mutex_destroy(&save_mutex);
	pthread_mutex_destroy(&new_game_mutex);
	return 0;
}